/**
 * 堆排序
 *
 * @param {number[]} nums
 * @return {number[]}
 */
function heapSort(nums) {
  let length = nums.length;
  if (length < 2) {
    return nums;
  }
  maxHeap(nums, length);
  for (let i = length - 1; i > 0; i--) {
    swap(nums, 0, i);
    length--;
    heapify(nums, length, 0);
  }
  return nums;
}

function maxHeap(nums, length) {
  for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
    heapify(nums, length, i);
  }
}

function heapify(nums, length, i) {
  const left = 2 * i + 1;
  const right = left + 1;
  let max = i;
  if (left < length && nums[left] > nums[max]) {
    max = left;
  }
  if (right < length && nums[right] > nums[max]) {
    max = right;
  }
  if (max != i) {
    swap(nums, max, i);
    heapify(nums, length, max);
  }
}

function swap(nums, i, j) {
  const temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

const nums = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(heapSort(nums));
